import UIKit

/*:
 # 动态规划

 动态规划的一般流程就是三步: 暴力的递归解法 -> 带备忘录的 递归解法 -> 迭代的动态规划解法。

 思考流程来说，就分为一下几步: 找到状态和选择 -> 明确 dp 数组/函数 的定义 -> 寻找状态之间的关系。

 动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最⻓递增子序列 呀，最小编辑距离呀等等。

 既然是要求最值，核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

 首先，动态规划的穷举有点特别，因为这类问题**存在「重叠子问题」**，如果 暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优 化穷举过程，避免不必要的计算。

 而且，动态规划问题一定会**具备「最优子结构」**，才能通过子问题的最值得 到原问题的最值。

 另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化， 穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方 程」**才能正确地穷举。

 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。


 */
